package leetcode.L1000;

import java.util.ArrayList;
import java.util.List;

class EX658 {

    public static void main(String[] args) {
        int[] arr = {0,0,0,1,3,5,6,7,8,8};
        int x = 2;
        int k = 2;

        int cur =  findpoint(arr,x);
        int left = cur;
        int right = cur;
        List<Integer> res = new ArrayList<Integer>();
        //问题出在这里，第一次已经默认一个数存在了，所以坑位少一
        for(int i = 0;i<k-1;i++){
            if(left-1<0){
                right = right +1;
            }
            else if(right+1>=arr.length){
                left = left - 1;
            }
            else if((x-arr[left-1])<=(arr[right+1]-x)){
                left = left - 1;
            }
            else{
                right = right+1;
            }
        }
        for(int i = left;i<=right;i++){
            res.add(arr[i]);
        }
        System.out.println(res);
    }
//    public List<Integer> findClosestElements(int[] arr, int k, int x) {
//        int cur =  findpoint(arr,x);
//        int left = cur;
//        int right = cur;
//        List<Integer> res = new ArrayList<Integer>();
//        for(int i = 0;i<k;i++){
//            if(left-1<0){
//                right = right +1;
//            }
//            else if(right+1>=arr.length){
//                left = left - 1;
//            }
//            else if((x-arr[left-1])<=(arr[right+1]-x)){
//                left = left - 1;
//            }
//            else{
//                right = right+1;
//            }
//        }
//        for(int i = left;i<right;i++){
//            res.add(arr[i]);
//        }
//        return res;
//    }

    public static int findpoint(int[] arr, int x){
        //先找到最接近点,由于要判断哪个点更加近，所以要一个闭区间，不能收敛到一个数。
        int left = 0,right = arr.length-1;
        int mid = 0;

        while(left+1<right){
            mid = left + (right - left)/2;
            if(arr[mid]==x){
                return mid;
            }
            else if(arr[mid]<x){
                left = mid;
            }
            else{
                right = mid;
            }

        }
        if((x-arr[left])<=(arr[right]-x)){
            return left;
        }
        else{
            return right;
        }
    }
}
